home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
TPUG - Toronto PET Users Group
/
TPUG Users Group CD
/
TPUG Users Group CD.iso
/
COMAL
/
Z-Misc Series
/
(k)zd.d64
/
txt.sets
< prev
Wrap
Text File
|
2007-03-01
|
6KB
|
291 lines
╙┼╘╙ ╔╬ ├╧═┴╠
BY ─ICK ╦LINGENS, ─UTCH ├╧═┴╠ ╒SERS
╟ROUP
╔N MATHEMATICS SETS ARE USED TO SOLVE
CERTAIN DISCRETE PROBLEMS. ╔N SOME
PROGRAMMING LANGUAGES (╨ASCAL, ┴─┴)
SETS ARE IMPLEMENTED TO DEAL WITH
SUCH PROBLEMS. ╔T IS POSSIBLE TO
CREATE SETS IN ├╧═┴╠ IN AN EASY WAY.
╔F AN ELEMENT IS A MEMBER OF A SET
(IS IN A SET), WE CAN RECORD THAT
WITH ╘╥╒┼ (ONE BIT); IF NOT WITH
╞┴╠╙┼. ╞OR 30 ELEMENTS WE NEED A
SEQUENCE OF 30 BITS, ONE FOR EACH
ELEMENT.
┼XAMPLE.
111111
12345678012345 <- ELEMENTS
--------------
00100000011100 <- BIT REPRESENTATION
OF THE SET
╫E HAVE A SET WITH ELEMENTS
3, 11, 12, 13, ...
╙UCH A BIT SEQUENCE CAN BE
REPRESENTED BY A REAL NUMBER: A SET
IS A REAL NUMBER. ╔N THE FOLLOWING WE
SHALL CREATE SETS WITH A MAXIMUM OF
30 ELEMENTS.
╫E NEED TWO FUNCTIONS; THE FIRST TO
TRANSFER A SET INTO A SEQUENCE OF
BITS (ONE'S AND ZERO'S IN A STRING)
AND THE SECOND TO TRANSFER A BIT
SEQUENCE INTO A SET.
// FROM SET TO BITS
╞╒╬├ BSTR$(NUMBER) ├╠╧╙┼─
─╔═ BINAR$ ╧╞ 30
BINAR$:=BIN$(NUMBER) // CONVERSION
╫╚╔╠┼ ╠┼╬(BINAR$)<30 ─╧
// ADD LEADING ZERO'S
BINAR$:="0"+BINAR$
┼╬─╫╚╔╠┼
╥┼╘╒╥╬ BINAR$
//
╞╒╬├ BIN$(NUMBER) ├╠╧╙┼─
╔╞ NUMBER=0 ╘╚┼╬
╥┼╘╒╥╬ ""
┼╠╙┼
╥┼╘╒╥╬ BIN$(NUMBER ─╔╓ 2)+
╙╘╥$(NUMBER ═╧─ 2)
┼╬─╔╞
┼╬─╞╒╬├ BIN$
┼╬─╞╒╬├ BSTR$
//
╞╒╬├ BVAL(BINAR$) ├╠╧╙┼─
╔╞ BINAR$="" ╘╚┼╬
╥┼╘╒╥╬ 0
┼╠╙┼
L:=╠┼╬(BINAR$)
╥┼╘╒╥╬ BVAL(BINAR$(1:L-1))*2+
╓┴╠(BINAR$(L:L))
┼╬─╔╞
┼╬─╞╒╬├ BVAL
╘O CREATE A SET OF ONE ELEMENT WE
HAVE
╞╒╬├ SETOF(ELEMENT) ├╠╧╙┼─
╔═╨╧╥╘ BSTR$,BVAL
─╔═ BINAR$ ╧╞ 30
BINAR$:=BSTR$(0) // ONLY ZERO'S
BINAR$(ELEMENT):="1"
╥┼╘╒╥╬ BVAL(BINAR$)
┼╬─╞╒╬├ SETOF
╒SING THIS FUNCTION:
SET1:=SETOF(2)
SET2:=SETOF(5)
WE HAVE THE SETS
(2) AND (5)
╫E CAN INCLUDE AN ELEMENT IN A SET BY
╞╒╬├ INCLUDE(SET,ELEMENT) ├╠╧╙┼─
╔═╨╧╥╘ BSTR$,BVAL
─╔═ BINAR$ ╧╞ 30
BINAR$:=BSTR$(SET)
BINAR$(ELEMENT):="1"
╥┼╘╒╥╬ BVAL(BINAR$)
┼╬─╞╒╬├ INCLUDE
┴ND NOW:
SET1:=INCLUDE(SET1,5)
SET2:=INCLUDE(INCLUDE(SET2,3),6)
╘HEN THE SETS ARE:
(2,5) AND (3,5,6)
╫ITH TWO OTHER FUNCTIONS WE CAN USE
THE SET OPERATIONS UNION AND SECTION.
╞╒╬├ UNION(SET1,SET2) ├╠╧╙┼─
╔═╨╧╥╘ BSTR$,BVAL
─╔═ BINAR1$ ╧╞ 30, BINAR2$ ╧╞ 30
BINAR1$:=BSTR$(SET1)
BINAR2$:=BSTR$(SET2)
╞╧╥ T:=1 ╘╧ 30 ─╧
╔╞ BINAR2$(T)="1" ╘╚┼╬
BINAR1$(T):="1"
┼╬─╔╞
┼╬─╞╧╥ T
╥┼╘╒╥╬ BVAL(BINAR1$)
┼╬─╞╒╬├ UNION
╞╒╬├ SECTION(SET1,SET2) ├╠╧╙┼─
╔═╨╧╥╘ BSTR$,BVAL
─╔═ BINAR1$ ╧╞ 30, BINAR2$ ╧╞ 30
BINAR1$:=BSTR$(SET1)
BINAR2$:=BSTR$(SET2)
╞╧╥ T:=1 ╘╧ 30 ─╧
╔╞ ╬╧╘ (BINAR1$(T)="1" ┴╬─
BINAR2$(T)="1" ╘╚┼╬
BINAR1$:="0"
┼╬─╔╞
┼╬─╞╧╥ T
╥┼╘╒╥╬ BVAL(BINAR1$)
┼╬─╞╒╬├ SECTION
╬OW:
UNI:=UNION(SET1,SET2)
SEC:=SECTION(SET1,SET2)
╫E CAN SHOW THE ELEMENTS OF A SET
WITH
╞╒╬├ ELEMENTS(SET) ├╠╧╙┼─
╔═╨╧╥╘ BSTR$
─╔═ BINAR$ ╧╞ 30
BINAR$:=BSTR$(SET)
NUM:=0 // NUMBER OF ELEMENTS
╞╧╥ T:=1 ╘╧ 30 ─╧
╔╞ BINAR$(T)="1" ╘╚┼╬
NUM:+1
╨╥╔╬╘ T; // ELEMENT
┼╬─╔╞
┼╬─╞╧╥ T
╨╥╔╬╘ "#",
╥┼╘╒╥╬ NUM
┼╬─╞╒╬├ ELEMENTS
┼XAMPLE.
╨╥╔╬╘ ELEMENTS(UNI)
╨╥╔╬╘ ELEMENTS(SEC)
WITH OUTPUT
2 3 5 6 #4
5 #1
WHERE THE NUMBER OF ELEMENTS OF THE
SET IS PRINTED AFTER #.
├REATION OF THE EMPTY SET (NO
ELEMENTS) IS POSSIBLE WITH
╞╒╬├ EMPTY ├╠╧╙┼─
╔═╨╧╥╘ BSTR$, BVAL
// OR SIMPLY ╥┼╘╒╥╬ 0
╥┼╘╒╥╬ BVAL(BSTR$(0))
┼╬─╞╒╬├ EMPTY
┴ NICE EXAMPLE, SHOWING REVERSED
POLISH NOTATION:
SET1:=EMPTY
SET2:=EMPTY
SET1:=INCLUDE(INCLUDE(INCLUDE
(SET1,3),4),5)
SET2:=INCLUDE(INCLUDE(INCLUDE
(SET2,4),5),6)
╨╥╔╬╘ ELEMENTS(UNION(SECTION(SET1,
SET2),INCLUDE(SET1,7))
┬ECAUSE A REAL NUMBER IS REPRESENTED
BY 5 BYTES, THE MAXIMUM NUMBER OF
ELEMENTS OF A SET IS 40 (5 TIMES 8
BITS).
╔F SETS WITH MORE THAN 40 ELEMENTS
ARE WANTED, ONE CAN USE ARRAY'S.
╨RCEDURES IN STEAD OF FUNCTIONS MUST
THEN BE USED.
╔T IS ALSO POSSIBLE TO USE STRINGS
LEAVING OUT THE CONVERSION INTO REAL
NUMBERS.
╔ GIVE SOME EXAMPLES IN THE FOLLWING
PROGRAM:
─╔═ A$ ╧╞ 80, B$ ╧╞ 80
─╔═ C$ ╧╞ 80, D$ ╧╞ 80
A$:=EMPTY$; B$:=EMPTY$
C$:=EMPTY$; D$:=EMPTY$
// 4 SETS ARE NOW CREATED; EACH
// WITH ROOM FOR 80 ELEMENTS
//
╞╒╬├ EMPTY$ ├╠╧╙┼─
─╔═ R$ ╧╞ 80
╞╧╥ T:=1 ╘╧ 80 ─╧ R$:+"0"
╥┼╘╒╥╬ R$
┼╬─╞╒╬├ EMPTY$
//
╞╒╬├ INCLUDE$(SET$,ELEMENT) ├╠╧╙┼─
SET$(ELEMENT:ELEMENT):="1"
╥┼╘╒╥╬ SET$
┼╬─╞╒╬├ INCLUDE$
// USING THIS FUNCTION:
//
A$:=INCLUDE$(INCLUDE$(A$,3),4)
B$:=INCLUDE$(INCLUDE$(B$,4),5)
B$:=INCLUDE$(B$,6)
//
╞╒╬├ ELEMENTS(SET$) ├╠╧╙┼─
NUM:=0
╞╧╥ T:=1 ╘╧ 80 ─╧
╔╞ SET$(T:T)="1" ╘╚┼╬
╨╥╔╬╘ T;
NUM:+1
┼╬─╔╞
┼╬─╞╧╥ T
╨╥╔╬╘ #,
╥┼╘╒╥╬ NUM
┼╬─╞╒╬├ ELEMENTS
// AND IT IS POSSIBLE TO PRINT THE
// ELEMENTS:
//
╨╥╔╬╘ ELEMENTS(A$)
╨╥╔╬╘ ELEMENTS(B$)
//
╞╒╬├ UNION$(SET1$,SET2$) ├╠╧╙┼─
─╔═ R$ ╧╞ 80
╞╧╥ T:=1 ╘╧ 80 ─╧
╔╞ SET2$(T:T)="1" ╘╚┼╬
SET1$(T:T):="1"
┼╬─╔╞
┼╬─╞╧╥ T
╥┼╘╒╥╬ SET1$
┼╬─╞╒╬├ UNION$
//
C$:=UNION$(A$,B$)
╨╥╔╬╘ ELEMENTS(C$)
//
╞╒╬├ SECTION$(SET1$,SET2$) ├╠╧╙┼─
╞╧╥ T:=1 ╘╧ 80 ─╧
╔╞ ╬╧╘ (SET1$(T:T)="1" ┴╬─
SET2$(T:T)="1") ╘╚┼╬
SET1$(T:T):="0"
┼╬─╔╞
┼╬─╞╧╥ T
╥┼╘╒╥╬ SET1$
┼╬─╞╒╬├ SECTION$
//
╨╥╔╬╘ ELEMENTS(SECTION$(A$,C$))
╨╥╔╬╘ ELEMENTS(SECTION$(B$,C$))
╬OW THE EXECUTION OF THIS PROGRAM IS
FASTER THAN FOR A PROGRAM WHICH
INCLUDES CONVERSION INTO REAL
NUMBERS. ┴ SECOND ADVANTAGE IS THAT
THE PROGRAM IS MORE READBLE. ╚OWEVER,
THERE IS MORE MEMORY OCCUPIED BY
STRINGS THAN BY REAL NUMBERS.
╔T IS LEFT TO INTERESTED READER TO
CONVERT REAL FUNCTIONS SUCH AS MINUS
AND SYMMINUS INTO STRING FUNCTIONS
FOR SET OPERATIONS.